/LMAR=50/TMAR=50/RMAR=4095/BMAR=1/PMAR=0/XLINE=0/FONT#0=NGR13/USETI=0000022*TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX*

␈β↓Y␈↓ ↓H␈εα4.x␈ε∞␈↓ ε3ARITH␈α␈METIC←FIRST␈αλPR␈α␈OOFS␈ε⊗␈α	⎇␈ε∞␈α	19␈α␈78␈↓ 
v␈εα701
␈βα∨␈↓ ↓4␈ε≥*␈↓ ↓H␈ε≥4␈α␈.7.␈α
MANIP␈α↓ULA␈α|TION␈α
OF␈α
P␈α↓O␈α}WER␈α
SERIES
␈βαd␈↓ ↓H␈εαI␈↓ βk␈εαt␈α␈w␈α␈o␈αpo␈α␈w␈α␈er␈αseries
␈βαi␈↓ ↓T␈ε∧F␈α
WE␈α
A␈α↓R␈α␈E␈αGIVE␈α↓N
␈ββ8␈↓ ¬≥␈ε¬2␈↓ 	N␈ε¬2
␈ββ>␈↓ α*␈ελU␈↓ αH␈εα(␈↓ αT␈ελz␈↓ αc␈εα)␈α
=␈↓ β'␈ελU␈↓ βT␈εα+␈↓ ∧␈ελU␈↓ ∧&␈ελz␈↓ ∧=␈εα+␈↓ ∧i␈ελU␈↓ ¬∞␈ελz␈↓ ¬3␈εα+␈↓ ¬←␈ε⊗↓␈αε↓␈αε↓␈↓ ε∂␈εα,␈↓ εg␈ελV␈↓ π↓␈εα(␈↓ π
␈ελz␈↓ π≤␈εα)␈α
=␈↓ π`␈ελV␈↓ λ␈εα+␈↓ λ7␈ελV␈↓ λY␈ελz␈↓ λp␈εα+␈↓ 	≤␈ελV␈↓ 	?␈ελz␈↓ 	d␈εα+␈↓ 
⊂␈ε⊗↓␈αε↓␈αε↓␈↓ 
@␈εα,␈↓ α␈εα(1)
␈ββK␈↓ β>␈ε¬0␈↓ ∧↔␈ε¬1␈↓ ¬␈ε¬2␈↓ πt␈ε¬0␈↓ λK␈ε¬1␈↓ 	0␈ε¬2
␈β∧↔␈↓ ↓H␈εαwhose␈αcoe}cien␈α␈ts␈α
belong␈α
to␈αa␈α
|eld,␈α
w␈α␈e␈αcan␈α
form␈α
their␈αsum,␈α
their␈α
product,␈αtheir
␈β∧B␈↓ ↓H␈εαquotien␈α␈t,␈α∞etc.,␈α∞to␈α∞obtain␈α∞new␈α∞po␈α␈w␈α␈er␈α∞series.␈α∩A␈α∞polynomial␈α∞is␈α∞obviously␈α∞a␈α
special
␈β∧n␈↓ ↓H␈εαcase␈αof␈αa␈αpo␈α␈w␈α␈er␈αseries,␈αin␈αwhich␈αthere␈αare␈αonly␈α|nitely␈αman␈α␈y␈αterms.
␈β¬~␈↓ α␈εαOf␈α	course,␈α	only␈αλa␈α	|nite␈αλn␈α␈um␈α␈ber␈α	of␈αλterms␈α	can␈αλbe␈α	represen␈α␈ted␈αλand␈α	stored␈αλwithin
␈β¬E␈↓ ↓H␈εαa␈α	computer,␈αso␈α	it␈α
mak␈α␈es␈α
sense␈α
to␈α	ask␈α
whether␈α
po␈α␈w␈α␈er␈α	series␈α
arithmetic␈α
is␈α
ev␈α␈en␈α	pos-
␈β¬p␈↓ ↓H␈εαsible␈α
on␈α
computers;␈αand␈α
if␈αit␈α
is␈α
possible,␈αwhat␈α
mak␈α␈es␈αit␈α
di{eren␈α␈t␈α
from␈α
polynomial
␈βε≠␈↓ ↓H␈εαarithmetic?␈αThe␈αansw␈α␈er␈αis␈αthat␈αw␈α␈e␈αw␈α␈ork␈αonly␈αwith␈αthe␈α|rst␈↓ λn␈ελN␈↓ 	≤␈εαcoe}cien␈α␈ts␈αof␈αthe
␈βεG␈↓ ↓H␈εαpo␈α␈w␈α␈er␈αseries,␈αwhere␈↓ ∧↓␈ελN␈↓ ∧/␈εαis␈αa␈αparameter␈αthat␈αmay␈αin␈αprinciple␈αbe␈αarbitrarily␈αlarge;
␈βεr␈↓ ↓H␈εαinstead␈α
of␈α
ordinary␈α∞polynomial␈α
arithmetic,␈α∞w␈α␈e␈α
are␈α∞essen␈α␈tially␈α
doing␈α
polynomial
␈βπ_␈↓ β|␈εN
␈βπ≥␈↓ ↓H␈εαarithmetic␈αλmodulo␈↓ βm␈ελz␈↓ ∧↔␈εα,␈α	and␈αλthis␈απoften␈αλleads␈αλto␈αλa␈αλseomewhat␈αλdi{eren␈α␈t␈αλpoin␈α␈t␈αλof␈απview.
␈βπH␈↓ ↓H␈εαFurthermore,␈αλspecial␈αλoperations␈αλlik␈α␈e␈αλ\rev␈α␈ersion"␈αλcan␈αλbe␈αλperformed␈αλon␈αλpo␈α␈w␈α␈er␈αλseries
␈βπs␈↓ ↓H␈εαbut␈α
not␈α
on␈α
polynomials,␈α
since␈α
polynomials␈α
are␈α
not␈α
closed␈α
under␈α
these␈α
operations.
␈βλ ␈↓ α␈εαManipulation␈αof␈αpo␈α␈w␈α␈er␈αseries␈αhas␈αsev␈α␈eral␈αapplications␈αto␈αn␈α␈umerical␈αanalysis,
␈βλK␈↓ ↓H␈εαbut␈α∞perhaps␈α
its␈α∞greatest␈α∞use␈α∞is␈α∞the␈α∞determination␈α∞of␈α∞asymptotic␈α∞expansions␈α
(as
␈βλv␈↓ ↓H␈εαw␈α␈e␈α⊂hav␈α␈e␈α⊃seen␈α⊂in␈α⊃Section␈α⊂1.2.11.3),␈α∩or␈α⊃the␈α⊂calculation␈α⊃of␈α⊂quan␈α␈tities␈α⊃de|ned␈α⊂by
␈β	!␈↓ ↓H␈εαcertain␈αgenerating␈αfunctions.␈αThe␈α
latter␈αapplications␈αmak␈α␈e␈αit␈αdesirable␈αto␈αcalcu-
␈β	M␈↓ ↓H␈εαlate␈αthe␈αcoe}cien␈α␈ts␈αexactly,␈αinstead␈αof␈αwith␈α⎇oating-poin␈α␈t␈αarithmetic.␈αAll␈αof␈αthe
␈β	x␈↓ ↓H␈εαalgorithms␈α
in␈α∞this␈α
section,␈α∞with␈α∞obvious␈α
ex␈α␈ceptions,␈α∞can␈α∞be␈α
done␈α∞using␈α
rational
␈β
#␈↓ ↓H␈εαoperations␈α
only,␈α
so␈α∞the␈α
techniques␈α
of␈α∞Section␈α
4.5.1␈α
can␈α
be␈α∞used␈α
to␈α
obtain␈α
exact
␈β
N␈↓ ↓H␈εαresults␈αwhen␈αdesired.
␈β
z␈↓ α␈εαThe␈α
calculation␈α
of␈↓ ∧:␈ελW␈↓ ∧]␈εα(␈↓ ∧i␈ελz␈↓ ∧x␈εα)␈α=␈↓ ¬@␈ελU␈↓ ¬↑␈εα(␈↓ ¬j␈ελz␈↓ ¬y␈εα)␈ε⊗␈α	ε␈↓ ε;␈ελV␈↓ εT␈εα(␈↓ ε`␈ελz␈↓ εo␈εα)␈α∞is,␈α
of␈α
course,␈α∞trivial,␈α
since␈α
w␈α␈e␈α
hav␈α␈e
␈β&␈↓ ↓H␈ελW␈↓ αα␈εα=␈↓ α0␈ελU␈↓ α←␈ε⊗ε␈↓ β	␈ελV␈↓ β9␈εαfor␈↓ βp␈ελn␈↓ ∧⊂␈εα=␈α
0,␈α1,␈α2,␈↓ ¬2␈εα.␈αε.␈αε.␈↓ ¬h␈εα.␈αIt␈αis␈α
also␈αeasy␈αto␈α
calculate␈↓ 	~␈ελW␈↓ 	>␈εα(␈↓ 	J␈ελz␈↓ 	Y␈εα)␈α
=␈↓ 
≥␈ελU␈↓ 
:␈εα(␈↓ 
F␈ελz␈↓ 
U␈εα)␈↓ 
a␈ελV␈↓ 
{␈εα(␈↓ π␈ελz␈↓ ⊗␈εα),
␈β3␈↓ ↓f␈εn␈↓ αG␈εn␈↓ β≥␈εn
␈βQ␈↓ ↓H␈εαusing␈αthe␈αfamiliar␈α\Cauch␈α␈y␈αproduct␈αrule":
␈βπ␈↓ ∧␈ε↓X
␈β*␈↓ β	␈ελW␈↓ βC␈εα=␈↓ ∧←␈ελU␈↓ ¬¬␈ελV␈↓ ¬`␈εα=␈↓ ε∞␈ελU␈↓ ε3␈ελV␈↓ εa␈εα+␈↓ π
␈ελU␈↓ π3␈ελV␈↓ λ␈εα+␈↓ λ8␈ε⊗↓␈αε↓␈αε↓␈↓ λj␈εα+␈↓ 	⊗␈ελU␈↓ 	?␈ελV␈↓ 	a␈εα.␈↓ α␈εα(2)
␈β8␈↓ β'␈εn␈↓ ∧v␈εk␈↓ ¬→␈εn␈↓ ¬+␈ε→␈␈↓ ¬H␈εk␈↓ ε%␈ε¬0␈↓ εG␈εn␈↓ π$␈ε¬1␈↓ πG␈εn␈↓ πY␈ε→␈␈ε¬␈α␈1␈↓ 	-␈εn␈↓ 	S␈ε¬0
␈β\␈↓ βq␈ε¬0␈ε→∀␈↓ ∧≤␈εk␈↓ ∧+␈ε→∀␈↓ ∧G␈εn
␈β
→␈↓ α␈εαThe␈α∂quotien␈α␈t␈↓ βh␈ελW␈↓ ∧␈εα(␈↓ ∧_␈ελz␈↓ ∧'␈εα)␈α∞=␈↓ ∧t␈ελU␈↓ ¬⊃␈εα(␈↓ ¬≥␈ελz␈↓ ¬,␈εα)/␈↓ ¬J␈ελV␈↓ ¬d␈εα(␈↓ ¬p␈ελz␈↓ ¬␈␈εα),␈α∂when␈↓ π¬␈ελV␈↓ π6␈ε⊗≤␈εα␈α∞0,␈α∂can␈α∂be␈α∞obtained␈α∂by␈α∞in␈α␈ter-
␈β
&␈↓ π→␈ε¬0
␈β
D␈↓ ↓H␈εαchanging␈↓ α`␈ελU␈↓ β	␈εαand␈↓ βO␈ελW␈↓ β␈␈εαin␈α(2);␈αw␈α␈e␈αobtain␈αthe␈αrule
␈β∞⊂␈↓ ¬β␈ε↓X
␈β∞→␈↓ βv␈ε↓∩␈↓ εU␈ε↓∪␈↓ εk␈ε↓≡
␈β∞3␈↓ β∞␈ελW␈↓ βH␈εα=␈↓ ∧␈ελU␈↓ ∧=␈ε⊗␈␈↓ ¬W␈ελW␈↓ ε∧␈ελV␈↓ π⊂␈ελV
␈β∞A␈↓ β,␈εn␈↓ ∧#␈εn␈↓ ¬u␈εk␈↓ ε_␈εn␈↓ ε)␈ε→␈␈↓ εF␈εk␈↓ π$␈ε¬0
␈β∞e␈↓ ∧i␈ε¬0␈ε→∀␈↓ ¬∀␈εk␈↓ ¬"␈ε¬<␈↓ ¬?␈εn
␈β∂⊗␈↓ βH␈εα=␈α
(␈↓ ∧α␈ελU␈↓ ∧3␈ε⊗␈␈↓ ∧←␈ελW␈↓ ¬␈ελV␈↓ ¬9␈ε⊗␈␈↓ ¬e␈ελW␈↓ ε⊃␈ελV␈↓ εj␈ε⊗␈␈↓ π⊗␈ε⊗↓␈αε↓␈αε↓␈↓ πH␈ε⊗␈␈↓ πt␈ελW␈↓ λP␈ελV␈↓ λr␈εα)/␈↓ 	⊂␈ελV␈↓ 	2␈εα.␈↓ α␈εα(3)
␈β∂#␈↓ ∧→␈εn␈↓ ∧⎇␈ε¬0␈↓ ¬∨␈εn␈↓ εβ␈ε¬1␈↓ ε%␈εn␈↓ ε7␈ε→␈␈ε¬1␈↓ λ∩␈εn␈↓ λ$␈ε→␈␈ε¬1␈↓ λd␈ε¬1␈↓ 	$␈ε¬0
␈β∂o␈↓ ↓H␈εαThis␈αrecurrence␈αrelation␈αfor␈αthe␈↓ ¬@␈ελW␈↓ ¬d␈εα's␈αmak␈α␈es␈αit␈αeasy␈αto␈αdetermine␈↓ 	<␈ελW␈↓ 	h␈εα,␈↓ 	}␈ελW␈↓ 
*␈εα,␈↓ 
@␈ελW␈↓ 
m␈εα,␈↓ α␈εα.␈αε.␈αε.
␈β∂⎇␈↓ 	Z␈ε¬0␈↓ 
≤␈ε¬1␈↓ 
↑␈ε¬2
␈β⊂~␈↓ ↓H␈εαsuccessiv␈α␈ely,␈αwithout␈αinputting␈↓ ¬9␈ελU␈↓ ¬n␈εαand␈↓ ε3␈ελV␈↓ εe␈εαun␈α␈til␈αafter␈↓ λ∂␈ελW␈↓ λu␈εαhas␈αbeen␈αcomputed.
␈β⊂(␈↓ ¬P␈εn␈↓ εG␈εn␈↓ λ-␈εn␈↓ λ?␈ε→␈␈ε¬␈α␈1
␈β⊂F␈↓ ↓H␈εαLet␈αus␈α
say␈αthat␈α
a␈α
po␈α␈w␈α␈er-series␈αmanipulation␈α
algorithm␈α
with␈αthe␈α
latter␈αproperty
␈β⊂q␈↓ ↓H␈εαis␈α∞\on-line";␈α⊂an␈α∂on-line␈α∞algorithm␈α∂can␈α∞be␈α∂used␈α∞to␈α∂determine␈↓ 	∞␈ελN␈↓ 	?␈εαcoe}cien␈α␈ts␈↓ 
v␈ελW␈↓ "␈εα,
␈β⊂}␈↓ ∀␈ε¬0
␈β⊃≤␈↓ ↓H␈ελW␈↓ ↓t␈εα,␈↓ α␈εα.␈αε.␈αε.␈↓ α;␈εα,␈↓ αQ␈ελW␈↓ βA␈εαof␈α
the␈αresult␈αwithout␈α
kno␈α␈wing␈↓ π$␈ελN␈↓ πR␈εαin␈αadvance,␈α
so␈αit␈α
is␈αpossible␈αin
␈β⊃)␈↓ ↓f␈ε¬1␈↓ αo␈εN␈↓ β
␈ε→␈␈ε¬␈α␈1
␈β∪(

␈β↓Y␈↓ ↓H␈εα702␈↓ α=␈ε∞A␈α␈RITH␈α␈METIC←FIRST␈α	P␈α␈ROOFS␈ε⊗␈α	⎇␈ε∞␈α	1␈α␈97␈α␈8␈εα␈↓ 
|4.x
␈βα(␈↓ ↓H␈εαtheory␈αto␈αrun␈αthe␈αalgorithm␈αinde|nitely␈αand␈αcompute␈αthe␈αen␈α␈tire␈αpo␈α␈w␈α␈er␈αseries;␈αor
␈βαS␈↓ ↓H␈εαto␈α	run␈α	it␈α	un␈α␈til␈α	a␈α
certain␈α	condition␈α	is␈α	met.␈α∪(The␈α	opposite␈α	of␈α	\on-line"␈α	is␈α	\o{-line.")
␈βα}␈↓ α␈εαIf␈α⊃the␈α⊃coe}cien␈α␈ts␈↓ ∧2␈ελU␈↓ ∧h␈εαand␈↓ ¬3␈ελV␈↓ ¬g␈εαare␈α⊃in␈α␈tegers␈α⊃but␈α⊃the␈↓ λ<␈ελW␈↓ λy␈εαare␈α⊃not,␈α∩recurrence
␈ββ␈↓ ∧I␈εk␈↓ ¬G␈εk␈↓ λZ␈εk
␈ββ*␈↓ ↓H␈εα(3)␈α
in␈α␈v␈α␈olv␈α␈es␈αcomputation␈α
with␈α
fractions.␈α∂This␈α
can␈α
be␈α
av␈α␈oided␈α
by␈α
the␈αall-in␈α␈teger
␈ββU␈↓ ↓H␈εαapproach␈αdescribed␈αin␈αex␈α␈ercise␈α2.
␈ββ{␈↓ 	b␈ε
␈β∧␈↓ α␈εαLet␈α∞us␈α
no␈α␈w␈α
consider␈α∞the␈α
operation␈α∞of␈α
computing␈↓ λ→␈ελW␈↓ λ=␈εα(␈↓ λI␈ελz␈↓ λX␈εα)␈α=␈↓ 	!␈ελV␈↓ 	;␈εα(␈↓ 	G␈ελz␈↓ 	V␈εα)␈↓ 	r␈εα,␈α∞where␈↓ 
s␈ελ␈↓ ∀␈εαis
␈β∧+␈↓ ↓H␈εαan␈α	\arbitrary"␈α
po␈α␈w␈α␈er.␈αFor␈α
example,␈α
w␈α␈e␈α	could␈α
calculate␈α
the␈α	square␈α
root␈α	of␈↓ 
:␈ελV␈↓ 
T␈εα(␈↓ 
`␈ελz␈↓ 
o␈εα)␈α	by
␈β∧Q␈↓ ¬{␈ε→␈␈ε¬10␈↓ λ↓␈ε→
␈β∧S␈↓ βλ␈ε¬1
␈β∧V␈↓ ↓H␈εαtaking␈↓ α8␈ελ␈↓ αV␈εα=␈↓ β~␈εα,␈α
or␈αw␈α␈e␈αcould␈α|nd␈↓ ¬:␈ελV␈↓ ¬T␈εα(␈↓ ¬`␈ελz␈↓ ¬o␈εα)␈↓ εA␈εαor␈αev␈α␈en␈↓ π@␈ελV␈↓ πZ␈εα(␈↓ πf␈ελz␈↓ πu␈εα)␈↓ λ⊃␈εα.␈α
If␈↓ λL␈ελV␈↓ 	ε␈εαis␈αthe␈α|rst␈αnonzero
␈β∧d␈↓ λ`␈εm
␈β∧g␈↓ βλ␈∧∧gβλα∂
␈β∧i␈↓ βλ␈ε¬2
␈β¬α␈↓ ↓H␈εαcoe}cien␈α␈t␈αof␈↓ β→␈ελV␈↓ β3␈εα(␈↓ β?␈ελz␈↓ βN␈εα),␈αw␈α␈e␈αhav␈α␈e
␈β¬≥␈↓ ∧N␈ε↓␈␈↓ 	H␈ε↓↓
␈β¬6␈↓ ∧4␈εm␈↓ λV␈ε¬2
␈β¬<␈↓ α}␈ελV␈↓ β_␈εα(␈↓ β$␈ελz␈↓ β3␈εα)␈↓ βI␈εα=␈↓ βw␈ελV␈↓ ∧%␈ελz␈↓ ∧\␈εα1␈αλ+␈αλ(␈↓ ¬.␈ελV␈↓ επ␈εα/␈↓ ε→␈ελV␈↓ εG␈εα)␈↓ εS␈ελz␈↓ εj␈εα+␈αλ(␈↓ π"␈ελV␈↓ π{␈εα/␈↓ λ
␈ελV␈↓ λ;␈εα)␈↓ λG␈ελz␈↓ λl␈εα+␈↓ 	_␈ε⊗↓␈αε↓␈αε↓␈↓ 	V␈εα,
␈β¬J␈↓ ∧␈εm␈↓ ¬B␈εm␈↓ ¬\␈ε¬+␈α␈1␈↓ ε-␈εm␈↓ π6␈εm␈↓ πP␈ε¬+␈α␈2␈↓ λ!␈εm
␈β¬S␈↓ ∧d␈ε↓␈␈↓ 	↑␈ε↓↓
␈β¬W␈↓ α␈εα(4)
␈β¬e␈↓ 	l␈ε
␈β¬l␈↓ β/␈ε␈↓ ∧⊃␈ε␈↓ ∧:␈ε␈↓ ∧J␈εm␈↓ λl␈ε¬2
␈β¬r␈↓ αn␈ελV␈↓ βλ␈εα(␈↓ β∀␈ελz␈↓ β#␈εα)␈↓ βI␈εα=␈↓ βw␈ελV␈↓ ∧+␈ελz␈↓ ∧r␈εα1␈αλ+␈αλ(␈↓ ¬D␈ελV␈↓ ε≥␈εα/␈↓ ε/␈ελV␈↓ ε]␈εα)␈↓ εi␈ελz␈↓ π␈εα+␈αλ(␈↓ π8␈ελV␈↓ λ⊃␈εα/␈↓ λ#␈ελV␈↓ λQ␈εα)␈↓ λ]␈ελz␈↓ 	α␈εα+␈↓ 	.␈ε⊗↓␈αε↓␈αε↓␈↓ 	|␈εα.
␈βε␈↓ ¬X␈εm␈↓ ¬r␈ε¬+␈α␈1␈↓ εC␈εm␈↓ πL␈εm␈↓ πf␈ε¬+2␈↓ λ7␈εm
␈βε∧␈↓ ∧⊃␈εm
␈βε,␈↓ ↓H␈εαThis␈αwill␈αbe␈α
a␈αpo␈α␈w␈α␈er␈α
series␈αif␈αand␈α
only␈αif␈↓ εR␈ελ␈↓ εf␈ελm␈↓ π∩␈εαis␈αa␈αnonnegativ␈α␈e␈α
in␈α␈teger.␈α
From␈α(4)
␈βεW␈↓ ↓H␈εαw␈α␈e␈αcan␈αsee␈αthat␈αthe␈αproblem␈αof␈αcomputing␈αgeneral␈αpo␈α␈w␈α␈ers␈αcan␈αbe␈αreduced␈αto␈αthe
␈βπα␈↓ ↓H␈εαcase␈αthat␈↓ αb␈ελV␈↓ β∞␈εα=␈α
1;␈αthen␈αthe␈αproblem␈αis␈αto␈α|nd␈αcoe}cien␈α␈ts␈αof
␈βπ∂␈↓ αv␈ε¬0
␈βπ5␈↓ εj␈ε¬2␈↓ π↑␈ε¬3␈↓ λ\␈ε
␈βπ<␈↓ β}␈ελW␈↓ ∧"␈εα(␈↓ ∧.␈ελz␈↓ ∧=␈εα)␈α
=␈α
(1␈αλ+␈↓ ¬S␈ελV␈↓ ¬u␈ελz␈↓ ε␈εα+␈↓ ε8␈ελV␈↓ ε[␈ελz␈↓ π␈εα+␈↓ π,␈ελV␈↓ πO␈ελz␈↓ πt␈εα+␈↓ λ ␈ε⊗↓␈αε↓␈αε↓␈↓ λP␈εα)␈↓ λl␈εα.␈↓ α␈εα(5)
␈βπI␈↓ ¬g␈ε¬1␈↓ εL␈ε¬2␈↓ π@␈ε¬3
␈βπp␈↓ β>␈ε
␈βπu␈↓ ↓H␈εαClearly␈↓ αH␈ελW␈↓ α}␈εα=␈↓ β,␈εα1␈↓ βX␈εα=␈α
1.
␈βλα␈↓ αf␈ε¬0
␈βλ ␈↓ α␈εαThe␈α
obvious␈α	way␈α
to␈α
|nd␈α	the␈α
coe}cien␈α␈ts␈α
of␈α	(5)␈α
is␈α
to␈α	use␈α
the␈α
binomial␈α	theorem
␈βλK␈↓ ↓H␈εα(Eq.␈α
1.2.9↑19),␈α
or␈α
(if␈↓ ∧λ␈ελ␈↓ ∧%␈εαis␈α
a␈α
positiv␈α␈e␈α
in␈α␈teger)␈α
to␈α
try␈α
repeated␈α
squaring␈α
as␈α
in␈α	Section
␈βλw␈↓ ↓H␈εα4.6.3;␈α∂but␈α∞a␈α∞m␈α␈uch␈α∞simpler␈α∞and␈α∂more␈α∞e}cien␈α␈t␈α∞device␈α∞for␈α∞calculating␈α∞po␈α␈w␈α␈ers␈α∞has
␈β	"␈↓ ↓H␈εαbeen␈α
suggested␈α
by␈α
J.␈α
C.␈α∞P.␈α
Miller.␈α≠[See␈α
P.␈α∞Henrici,␈ε∂␈α
JA␈α␈CM␈ε∩␈α
3␈εα␈α∞(1956),␈α
10↑15.]␈α≠If
␈β	H␈↓ β␈ε
␈β	M␈↓ ↓H␈ελW␈↓ ↓l␈εα(␈↓ ↓x␈ελz␈↓ απ␈εα)␈α
=␈↓ αK␈ελV␈↓ αe␈εα(␈↓ αq␈ελz␈↓ β␈εα)␈↓ β≤␈εα,␈αw␈α␈e␈αhav␈α␈e␈αby␈αdi{eren␈α␈tiation
␈β
␈↓ ¬I␈ε¬2␈↓ π∩␈ε→0␈↓ λM␈ε␈↓ λ]␈ε→␈␈ε¬1␈↓ 	"␈ε→0
␈β
π␈↓ β~␈ελW␈↓ βN␈εα+␈αλ2␈↓ ∧␈ελW␈↓ ∧9␈ελz␈↓ ∧P␈εα+␈αλ3␈↓ ¬∞␈ελW␈↓ ¬:␈ελz␈↓ ¬`␈εα+␈↓ ε␈ε⊗↓␈αε↓␈αε↓␈↓ ε@␈εα=␈↓ εn␈ελW␈↓ π→␈εα(␈↓ π%␈ελz␈↓ π4␈εα)␈α
=␈↓ πx␈ελ␈↓ λ␈ελV␈↓ λ&␈εα(␈↓ λ2␈ελz␈↓ λA␈εα)␈↓ 	λ␈ελV␈↓ 	)␈εα(␈↓ 	5␈ελz␈↓ 	D␈εα);␈↓ α␈εα(6)
␈β
∀␈↓ β8␈ε¬1␈↓ ∧*␈ε¬2␈↓ ¬,␈ε¬3
␈β
@␈↓ ↓H␈εαtherefore
␈β
e␈↓ ¬ ␈ε→0␈↓ π@␈ε→0
␈β
k␈↓ ∧|␈ελW␈↓ ¬'␈εα(␈↓ ¬3␈ελz␈↓ ¬B␈εα)␈↓ ¬N␈ελV␈↓ ¬h␈εα(␈↓ ¬t␈ελz␈↓ εβ␈εα)␈α
=␈↓ εG␈ελ␈↓ ε[␈ελW␈↓ ε␈␈εα(␈↓ π␈ελz␈↓ π~␈εα)␈↓ π&␈ελV␈↓ πG␈εα(␈↓ πS␈ελz␈↓ πb␈εα).␈↓ α␈εα(7)
␈β≡␈↓ ε
␈εn␈↓ ε≤␈ε→␈␈ε¬␈α␈1
␈β#␈↓ ↓H␈εαIf␈αw␈α␈e␈αno␈α␈w␈αequate␈αthe␈αcoe}cien␈α␈ts␈αof␈↓ ¬{␈ελz␈↓ εS␈εαin␈α(7),␈αw␈α␈e␈α|nd␈αthat
␈β=␈↓ βz␈ε↓X␈↓ εJ␈ε↓X
␈β`␈↓ ∧O␈ελk␈↓ ∧`␈ελW␈↓ ¬
␈ελV␈↓ ¬h␈εα=␈↓ ε⊗␈ελ␈↓ π→␈εα(␈↓ π%␈ελn␈↓ πB␈ε⊗␈␈↓ πn␈ελk␈↓ λ␈εα)␈↓ λ␈ελW␈↓ λ9␈ελV␈↓ 	
␈εα,␈↓ α␈εα(8)
␈βm␈↓ ∧}␈εk␈↓ ¬!␈εn␈↓ ¬3␈ε→␈␈↓ ¬P␈εk␈↓ λ*␈εk␈↓ λM␈εn␈↓ λ↑␈ε→␈␈↓ λ{␈εk
␈β⊃␈↓ β`␈ε¬0␈ε→␈α↓∀␈↓ ∧␈εk␈↓ ∧~␈ε→∀␈↓ ∧7␈εn␈↓ ε0␈ε¬0␈ε→␈α↓∀␈↓ ε[␈εk␈↓ εj␈ε→∀␈↓ ππ␈εn
␈βO␈↓ ↓H␈εαand␈αthis␈αgiv␈α␈es␈αus␈αa␈αuseful␈αcomputational␈αrule␈αvalid␈αfor␈αall␈↓ λ[␈ελn␈↓ λz␈ε⊗∃␈εα␈α
1,
␈βy␈↓ β ␈ε↓X
␈β
α␈↓ βt␈ε↓∩␈↓ ∧
␈ε↓∩␈↓ ¬α␈ε↓∪␈↓ ¬u␈ε↓∪
␈β
¬␈↓ ∧$␈ελ␈↓ ∧@␈εα+␈αλ1
␈β
≤␈↓ α≥␈ελW␈↓ αW␈εα=␈↓ ¬≡␈ελk␈↓ ¬7␈ε⊗␈␈εα␈αλ1␈↓ ε⊃␈ελV␈↓ ε4␈ελW
␈β
)␈↓ α;␈εn␈↓ ε%␈εk␈↓ εR␈εn␈↓ εd␈ε→␈␈↓ π↓␈εk
␈β
,␈↓ ∧$␈∧
,∧$αZ
␈β
4␈↓ ∧F␈ελn
␈β
M␈↓ β¬␈ε¬1␈ε→␈α↓∀␈↓ β1␈εk␈↓ β?␈ε→∀␈↓ β\␈εn
␈β
b␈↓ β¬␈ε↓␈␈↓ 	m␈ε↓↓
␈β∞α␈↓ αW␈εα=␈↓ β∪␈εα(␈↓ β∨␈ελ␈↓ β3␈εα+1␈ε⊗␈␈↓ ∧
␈ελn␈↓ ∧#␈εα)␈↓ ∧/␈ελV␈↓ ∧Q␈ελW␈↓ ¬4␈εα+␈αλ(2␈↓ ¬}␈ελ␈↓ ε∩␈εα+2␈ε⊗␈␈↓ εl␈ελn␈↓ πα␈εα)␈↓ π∞␈ελV␈↓ π0␈ελW␈↓ λ∪␈εα+␈↓ λ?␈ε⊗↓␈αε↓␈αε↓␈↓ λq␈εα+␈↓ 	≥␈ελn␈↓ 	3␈ελ␈↓ 	G␈ελV␈↓ 	{␈εα/␈↓ 

␈ελn␈↓ 
#␈εα.␈↓ α␈εα(9)
␈β∞∂␈↓ ∧C␈ε¬1␈↓ ∧o␈εn␈↓ ¬↓␈ε→␈␈ε¬1␈↓ π"␈ε¬2␈↓ πN␈εn␈↓ π`␈ε→␈␈ε¬2␈↓ 	[␈εn
␈β∞;␈↓ ↓H␈εαThis␈αequation␈α
leads␈αto␈α
a␈αsimple␈α
on-line␈α
algorithm␈αby␈α
which␈αw␈α␈e␈α
can␈αsuccessiv␈α␈ely
␈β∞g␈↓ ↓H␈εαdetermine␈↓ αq␈ελW␈↓ β≥␈εα,␈↓ β5␈ελW␈↓ βa␈εα,␈↓ βx␈εα.␈αε.␈αε.␈↓ ∧(␈εα,␈α∞using␈α
appro␈α␈ximately␈α
2␈↓ π!␈ελn␈↓ πD␈εαm␈α␈ultiplications␈α
to␈α
compute␈α
the
␈β∞t␈↓ β∂␈ε¬1␈↓ βS␈ε¬2
␈β∂∩␈↓ ↓H␈ελn␈↓ ↓]␈εαth␈α
coe}cien␈α␈t.␈α
Note␈αthe␈αspecial␈α
case␈↓ ε∃␈ελ␈↓ ε4␈εα=␈ε⊗␈α
␈␈εα1,␈α
in␈αwhich␈α(9)␈α
becomes␈αthe␈αspecial
␈β∂=␈↓ ↓H␈εαcase␈↓ α∀␈ελU␈↓ α1␈εα(␈↓ α=␈ελz␈↓ αL␈εα)␈α
=␈↓ β⊂␈ελV␈↓ β=␈εα=␈α
1␈αof␈α(3).
␈β∂I␈↓ π↔␈ε↓␈␈↓ πf␈ε↓↓
␈β∂J␈↓ β$␈ε¬0
␈β∂h␈↓ α␈εαA␈αsimilar␈α
technique␈αcan␈αbe␈αused␈α
to␈αform␈↓ πε␈ελf␈↓ π%␈ελV␈↓ π?␈εα(␈↓ πK␈ελz␈↓ πZ␈εα)␈↓ π␈␈εαwhen␈↓ λ[␈ελf␈↓ λw␈εαis␈αan␈α␈y␈αfunction␈α
that
␈β⊂∪␈↓ ↓H␈εαsatis|es␈αλa␈α	simple␈α	di{eren␈α␈tial␈α	equation.␈α⊃(For␈α	example,␈α
see␈αλex␈α␈ercise␈α	4.)␈α∩A␈αλcompara-
␈β⊂?␈↓ ↓H␈εαtiv␈α␈ely␈α
straigh␈α␈tforward␈α	\po␈α␈w␈α␈er-series␈α
method"␈α
is␈α
often␈α
used␈α
to␈α
obtain␈α
the␈α	solution
␈β⊂j␈↓ ↓H␈εαof␈α	di{eren␈α␈tial␈α	equations;␈αthis␈α	technique␈α	is␈α
explained␈α	in␈α	nearly␈α
all␈α	textbooks␈α	about
␈β⊃∃␈↓ ↓H␈εαdi{eren␈α␈tial␈αequations.
␈β∪(

␈β↓Y␈↓ ↓H␈εα4.x␈ε∞␈↓ ε6ARIT␈α␈HMET␈α␈IC←FIR␈α↓ST␈αλPR␈α␈OOFS␈↓ 
↓␈ε∞19␈α␈78␈↓ 
v␈εα801
␈β↓\␈↓ 	W␈ε↔⎇
␈β∪(/FONT#1=cmathx[XGP,SYS]=↓∩∪≡XX/FONT#2=cmr10[XGP,SYS]="'()+,-./0123456789:;=?ACEFHIJLMNOPST[\]↑abcdefghiklmnopqrstuvwxyz{|⎇}}/FONT#4=cmr8[XGP,SYS]=AEFGINRVWW/FONT#5=cmr7[XGP,SYS]=+0123<</FONT#8=cmi10[XGP,SYS]=NUVWfkmnzz/FONT#11=cmi7[XGP,SYS]=→Nkmnn/FONT#14=cmsc10[XGP,SYS]=1789ACEFHIMOPRST←←/FONT#15=cms10[XGP,SYS]=ACJMM/FONT#18=cmb10[XGP,SYS]=33/FONT#22=cmsy10[XGP,SYS]=↓ε∃≤⎇⎇/FONT#23=cmsy9[XGP,SYS]=⎇⎇/FONT#25=cmsy7[XGP,SYS]=∀00/FONT#29=cmssb[XGP,SYS]=*.47AEFILMNOPRSTUWW